#include <stdlib.h>
#include <iostream>

using namespace std;

#define max(a,b) (((a)<(b))?(b):(a))
#define min(a,b) (((a)<(b))?(a):(b))

#include "../general/hashtable.h"

class picture {
  public:
    string key;
    int data;
    picture *higher;
    picture *lower;
    picture(std::string k);
};

picture::picture(std::string k) {
    static int nr=0;
    data=++nr;
    higher=NULL;
    lower=NULL;
    key=k;
}

class cache {
  private:
    picture *lowest;
    picture *highest;
    int elements;
  public:
    cache();
    hashtable<const char,picture> data;
    picture &operator[](std::string key);
    bool exists(std::string key);
    void clean(int max);
    void dump();
};

cache::cache(): data(1000) {
    lowest=NULL;
    highest=NULL;
    elements=0;
}

picture& cache::operator[](std::string key) {
    picture *n=data[key.c_str()];
    if (n==NULL) {
        elements++;
        n=new picture(key);
        data.insert(key.c_str(), n);
    } else {
        if (n->lower != NULL) {
            n->lower->higher=n->higher;
        } else {
            lowest=n->higher;
        }
        if (n->higher != NULL) {
            n->higher->lower=n->lower;
            n->higher=NULL;
        }
    }
    n->lower=highest;
    if (highest != NULL) highest->higher=n;
    if (lowest == NULL) lowest=n;
    highest=n;
    return *n;
}

bool cache::exists(std::string key) {
    return data[key.c_str()]!=NULL;
}

void cache::clean(int m) {
    int t;
    int cnr=min(elements-m,10);
    for (t=0; t<cnr; t++) {
        picture *n=lowest->higher;
        data.remove(lowest->key.c_str());
        delete lowest;
        if (n!=NULL) n->lower=NULL;
        else highest=NULL;
        lowest=n;
        elements--;
    }
}

void cache::dump() {
    picture *n=highest;
    cout << "Dump with " << elements << " elements\n";
    while(n!=NULL) {
        cout << "  " << n->key << "=" << n->data << endl;
        if (n->lower != NULL) {
            if (n->lower->higher != n) {
                cout << "  Something is rotten\n";
            }
        } else {
            if (n != lowest) {
                cout << "  Highest isn't correct\n";
            }
        }
        n=n->lower;
    }
    cout << "Finished\n\n";
}
#define max_dither 37
unsigned int dither[max_dither];

int variant(int nr, int max) {
    int res=0;
    switch (max) {
        case 2:
            res=dither[nr]/128;
            break;
        case 3:
            res=dither[nr]/85;
            break;
        case 4:
            res=dither[nr]/64;
            break;
        case 5:
            res=dither[nr]/51;
            break;
        case 6:
            res=dither[nr]/42;
            break;
        case 7:
            res=dither[nr]/36;
            break;
        case 8:
            res=dither[nr]/32;
            break;
        case 9:
            res=dither[nr]/28;
            break;
        case 10:
            res=dither[nr]/25;
    }
    if (res>=max) res=max-1;
    return res;
}

int rand() {
    return random() / (RAND_MAX/256);
}

class pos {
  public:
    pos(std::string p);
    pos(int ix=0, int iy=0) { x=ix; y=iy; };
    int x:16;
    int y:16;
};

int fvariant(pos p, int max) {
    srandom(p.x+p.y*1000);
    int res=random() / (RAND_MAX/max);
    if (res>=max) res=max-1;
    return res;
}

int main() {
    int nr;
    int total=0;
    for (nr=0; nr<max_dither; nr++) {
        int c=0;
        unsigned int n=rand();
        cout << nr << "=" <<n << ":";
        if (nr>4 && nr<=6) {
            while (n/85 == dither[nr-5]/85 || n/51 == dither[nr-5]/51) {
                n=rand();
                cout << n << ":";
                c++;
            }
        }
        if (nr>6) {
            while (n/85 == dither[nr-5]/85 || n/51 == dither[nr-5]/51 ||
                   n/85 == dither[nr-7]/85 || n/51 == dither[nr-7]/51) {
                n=rand();
                cout << n << ":";
                c++;
            }
        }
        cout << c << endl;
        dither[nr]=n;
        total+=n;
    }
    int ntotal=0;
    for (nr=0; nr<max_dither; nr++) {
        ntotal+=dither[nr];
        cout << dither[nr] << ", ";
    }
    cout << endl;
    for (nr=2; nr<11; nr++) {
        cout << "Test set "<<nr<<" = ";
        int c;
        for (c=0; c<max_dither; c++) {
            cout <<variant(c, nr) << ",";
        }
        cout << endl;
    }
    cout << "Avg: " << ntotal/max_dither << endl;
    int v;
    for (v=2; v<11; v++) {
    cout << "Variant "<<v<<endl;
    for (nr=0; nr<max_dither; nr++) {
        int c;
        for (c=0; c<max_dither; c++) {
            cout << fvariant(pos(c,nr), v) << " ";
        }
        cout << endl;
    }
    }
    cache test;
    test["Hallo"].data=1;
    test.dump();
    test["Tot ziens"].data=2;
    test.dump();
    cout << "Test " << test["Hallo"].data << endl;
    test.dump();
    test.clean(1);
    test.dump();
    test.clean(0);
    test.dump();
}
